0067. 二进制求和【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟求和

1. 📝 题目描述

• leetcode

给你两个二进制字符串 a 和 b，以二进制字符串的形式返回它们的和。

---

示例 1：

输入:a = "11", b = "1"
输出："100"

---

示例 2：

输入：a = "1010", b = "1011"
输出："10101"

---

提示：

• 1 <= a.length, b.length <= 10^4
• a 和 b 仅由字符 '0' 或 '1' 组成
• 字符串如果不是 "0"，就不含前导零

2. 🎯 s.1 - 模拟求和

1.js

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
  let result = ''
  let carry = 0
  let i = a.length - 1
  let j = b.length - 1

  // 从右到左逐位相加
  while (i >= 0 || j >= 0 || carry > 0) {
    const digitA = i >= 0 ? parseInt(a[i]) : 0
    const digitB = j >= 0 ? parseInt(b[j]) : 0

    const sum = digitA + digitB + carry
    result = (sum % 2) + result
    carry = Math.floor(sum / 2)

    i--
    j--
  }

  return result
}

• 时间复杂度：$O(max(m,n))$，其中 m 和 n 分别是字符串 a 和 b 的长度，需要遍历较长字符串的所有位
• 空间复杂度：$O(max(m,n))$，结果字符串的长度最多为 $max(m,n)+1$

模拟二进制加法的手工计算过程。从两个字符串的末尾开始逐位相加，用变量 carry 记录进位，每次计算当前位的和并更新进位，最后将结果拼接成字符串返回。